
class ListNode1 {
    int val;
    ListNode1 next;

    ListNode1() {
    }

    ListNode1(int val) {
        this.val = val;
    }

    ListNode1(int val, ListNode1 next) {
        this.val = val;
        this.next = next;
    }
}

class Solution1 {
    public void reorderList(ListNode1 head) {
        //处理边界情况
        if (head == null || head.next == null || head.next.next == null){
            return;
        }
        //先找出链表中间节点（利用快慢指针）
        ListNode1 fast = head;
        ListNode1 slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode1 cur = slow.next;
        slow.next = null;
        //定义一个虚拟节点
        ListNode1 head2 = new ListNode1(0);
        //利用头插法
        while (cur != null){
            //先提前记录下一个结点的值
            ListNode1 curNext = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = curNext;
        }
        //合并两个链表
        ListNode1 cur1 = head,cur2 = head2.next;
        //在定义一个虚拟头结点
        ListNode1 ret = new ListNode1(0);
        ListNode1 prev = ret;
        while (cur1 != null){
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;
            if (cur2 != null){
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }

    }
}

public class Test02 {
}
